%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Cryptography
%% http://code.google.com/p/crypto-book/
%%
%% Copyright (C) 2007--2010 David R. Kohel <David.Kohel@univmed.fr>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Revision Exercises}

Let $\cA$ be the alphabet $\{\tA,\tB,\tC,\tD,\tE\}$.  Given the message
{\tt A BAD CAB A DEAD DAD}, we form the strip--encoded plaintext
$$
M = {\tt ABADCABADEADDAD}
$$
by removing all characters not in the alphabet.

\begin{exercise}
Encipher the message $M$ using the substitution key
$K = {\tt BDEAC}$.  Find the inverse key and verify the correctness
by deciphering your ciphertext.
\end{exercise}

\begin{proof}[Solution]
Recall that the key $K = {\tt BDEAC}$ specifies the map
$\tA\mapsto\tB$, $\tB\mapsto\tD$, etc.  This results in the
enciphering
$$
M = {\tt ABADCABADEADDAD} \mapsto C = {\tt BDBAEBDBACBAABD}.
$$
\end{proof}

\begin{exercise}
Let $\cA \rightarrow \Z/5\Z$ be the bijection $\tA \mapsto 0,
\tB \mapsto 1, \dots, \tE \mapsto 4$.  Encipher the message $M$ using
the Vigen\`ere key $K = {\tt ADECB}$ in ECB mode, then encipher the
same message using the same key and initialization vector {\tt BBBB},
in CFB and OFB modes with the block length $n = 5$ and $r = 1$.  Rather
than bit sum, use summation in $\Z/5\Z$ for the feedback.  Verify the
correctness of your results by then deciphering the ciphertext.
\end{exercise}

\begin{proof}[Solution]
We make the identification $M = {\tt ABADCABADEADDAD} =
{\tt 010320103403303}$ over $\Z/5\Z$.  In the same way,
we write $K = {\tt ADECB} = {\tt 03421}$.  The enciphering in ECB
mode is then ${\tt 044030440001223} = {\tt AEEADAEEAAABCCD}$.
The enciphering in CBC mode begins with $C_0 = {\tt BBBBB} =
{\tt 11111}$, and since $E_K(C_{j-1}\oplus M_j) = C_{j-1}\oplus
E_K(M_j)$, we just add in the previous ciphertext block to get
$$
{\tt 11111100141441410132} = {\tt BBBBBBAABEBEEBEBABDC}.
$$
The application of this function $E_K$ to form the state vectors
$I_j$ is particularly weak, since only the first character of the
key $K$ and the first character of the initialization vector.
Since $K = {\tt A****}$, this means $I_j = {\tt B****}$, and so
the ciphertext output is
$$
{\tt BBBBBBCBEDBCBEABEEBE}.
$$
\end{proof}

\begin{exercise}
Let $K = [3,5,4,1,2]$ be a transposition key.  Encipher the
message $M$ in ECB mode and in CBC mode.  Verify the correctness of
your results by deciphering the ciphertext.
\end{exercise}

\begin{proof}[Solution]
The key $K = [3,5,4,1,2]$ specifies a transposition,
under which $M \mapsto {\tt ACDABAEDABDDAAD}$ in ECB mode.
If we use the addition $\oplus$ of the previous question for
the feedback, then we get ciphertext
$$
{\tt BBBBBACDABDADADCCAAC}.
$$
{\it Check this work carefully for errors -- no guarantees.}
\end{proof}

\begin{exercise}
Which of the modes of operation leaves Vigen\`ere ciphertext open
to attack by the Kasiski method?  Which mode of operation was used
for the block ciphers in the course assignments, and why?
\end{exercise}

\begin{proof}[Solution]
We made use of the ECB mode in order to preserve the structure
of a Vigen\`ere ciphertext.  This leaves this and other classical
cryptosystems open to classical attacks such as the Kasiski method.
\end{proof}

\subsection*{Mathematics of LFSR's}

Next we focus on some of the mathematical problems which arise
in stream ciphers and public key cryptography.  The problems given
are of a size which can be computed by hand, with minimal effort
if the proper method is used.

\begin{exercise}
Let $S$ be the set $\{x^6 + x + 1,  x^6 + x^3 + 1,
x^6 + x^5 + 1, x^6 + x^2 + 1\}$ of polynomials in $\F_2[x]$.
\begin{enumerate}
\item
Which of the polynomials are irreducible?
\item
Which of the polynomials are primitive?
\item
What are the periods of the linear feedback shift registers
with the above connections polynomials?
\item
$(*)$ The polynomial $g(x) = x^6 + x^5 + x^4 + x^3 + 1$ is not
irreducible.  What is its factorization, and what are the periods
of output sequence of a linear feedback shift register with $g(x)$
as connection polynomial and initial states $010011$, $010010$,
and $111111$?
\end{enumerate}
\end{exercise}

\begin{proof}[Solution]
Let $S$ be the set
$\{x^6 + x + 1,  x^6 + x^3 + 1, x^6 + x^5 + 1, x^6 + x^2 + 1\}$
of polynomials in $\F_2[x]$.

\begin{enumerate}
\item
The polynomials $x^6+x+1$,  $x^6+x^3+1$, and $x^6+x^5+1$
are irreducible, but $x^6+x^2+1 = (x^3+x+1)^2$.
\item
Of the three irreducible polynomials, we find that $x^6+x^3+1$
generates LFSR output of period $9$, so is not primitive.  The
other two irreducible polynomials generate output of period greater
than $21 = 63/3$, so must be primitive.
\item
The periods are therefore 63, 9, 63, and (at most) 14.  The
period of 14 can be determined for a specific value, but poor
choices, like {\tt 1101001} can result in a period of 7, since
the connection polynomial is not irreducible.
\item
The polynomial $g(x) = x^6 + x^5 + x^4 + x^3 + 1$ factors as
$(x^2+x+1)(x^4+x+1)$.  The LFSR outputs for initial states $010011$,
$010010$, and $111111$ with connection polynomial $g(x)$ are:
$$
\begin{array}{l}
010011100110000 010011100110000 01\dots\\
010010101000011 010010101000011 01\dots\\
111111000101110 111111000101110 11\dots
\end{array}
$$
These each have periods $15$, which equals $2^4-1$ (rather than
$2^6-1$, which would be the case if $g(x)$ where irreducible.)
\end{enumerate}
\end{proof}

\subsection*{Mathematics of RSA}

\begin{exercise}
Let $G = (\Z/15\Z)^*$.
\begin{enumerate}
\item
What are the elements of G?
\item
Show that $a = 2$ is a primitive element for $(\Z/3\Z)^*$
and $a = 3$ is a primitive element for $(\Z/5\Z)^*$.
\item
Find an element $a$ in $\Z$ which is primitive for both
$(\Z/3\Z)^*$ and $(\Z/5\Z)^*$.
\item
$(*)$ Why does it not make sense to speak of a primitive
element for $G$?
\item
$(*)$ How many elements $a$ of $G$ have the property of
being primitive for both $(\Z/3\Z)^*$ and $(\Z/5\Z)^*$?
\end{enumerate}
\end{exercise}

\begin{proof}[Solution]
\begin{enumerate}
\item
The elements of $(\Z/15\Z)^*$ are
$$
\{1,2,4,7,8,11,13,14\},
$$
the elements of $\Z/15\Z$ coprime to 3 and 5.
\item
Since $\{1,2\} = (\Z/3\Z)^*$ and $\{1,3,9=4,27=2\} = (\Z/5\Z)^*$,
2 and 3 are primitive elements for these moduli.
\item
The integer 8 is primitive in $(\Z/3\Z)^*$ and $(\Z/5\Z)^*$,
since 8 is a CRT lift of the pair $(2,3)$ in $\Z/3\Z \times \Z/5\Z$,
i.e. $8 \equiv 2 \bmod 3$ and $8 \equiv 3 \bmod 5$.
\item
There is no primitive element for $\Z/15\Z^*$ since no single
element generates all of them.  For instance the powers of 8 are:
$$
1,8,64=4,32=2,16=1,
$$
which generates a cycle of length only 4, whereas $(\Z/15\Z)^*$
has eight elements.
\item
The elements of $(\Z/15\Z)^*$ which are primitive for both
$(\Z/3\Z)^*$ and $(\Z/5\Z)^*$ are the two CRT images of the
pairs $(2,3)$ and $(2,2)$.
\end{enumerate}
\end{proof}

\subsection*{Mathematics of Diffie--Hellman}

\begin{exercise}
Let $G_1 = (\Z/89\Z)^*$ and $G_2 = (\Z/97\Z)^*$.
\begin{enumerate}
\item
Show that $7$ is a primitive element for $G_1$ and for $G_2$.
\item
Solve the discrete logarithm problem $\log_7(2)$ in $G_1$
and in $G_2$.
\item
$(*)$ Which discrete logarithm is harder, and why?
\end{enumerate}
\end{exercise}

\begin{proof}[Solution]
\begin{enumerate}
\item
To show that $7$ is a primitive element for $(\Z/89\Z)^*$ and
$(\Z/97\Z)^*$, we need to show that
$$
\begin{array}{rr}
7^{44} \not\equiv 1 \bmod 89 & 7^{48} \not\equiv 1 \bmod 97 \\
 7^{8} \not\equiv 1 \bmod 89 & 7^{32} \not\equiv 1 \bmod 97
\end{array}
$$
These values can be computed using products of successive squares
of $7$, e.g. $7^{44} = 7^{4}7^{8}7^{32}$, so $7^4 \equiv 87 \bmod 89$,
$7^8 \equiv (-2)^2 \equiv 4 \bmod 89$, $7^{16} \equiv 16 \bmod 89$.
Therefore $7^{44} \equiv -1 \bmod 89$, etc.
\item
We find $\log_7(2) = 48$ in $\F_{89}$ and $\log_7(2) = 94$ in
$\F_{97}$ using the baby-step, giant-step method.
\item
A discrete logarithm in $(\Z/97\Z)^*$ is theoretically easier
to solve because $96 = 2^5 3$, so we solve the discrete logarithms
using this factorization.
\end{enumerate}

\noindent
N.B. Verify that you can solve $\log_7(2)$ using $\log_{7^m}(2^m)$
where $m = 32,$ and $m = 48, 24, 12, 6, 3$, and at each of the latter
steps you only need to determine one additional bit of information.

\end{proof}

\subsection*{Mathematics of Shamir's Secret Sharing Scheme}

Recall the Lagrange interpolation theorem:
\begin{theorem}[Lagrange]
Let $k$ be a field and let $f(x)$ be a polynomial over $k$ of
degree less than $t$.  Given $t$ distinct elements $x_1$,
$x_2,\dots,x_t$ of $k$, then $f(x)$ equals
$$
\sum_{i=1}^t f(x_i) \prod_{\stackrel{\scr j=1}{\scr j\ne i}}^t
\frac{x-x_j}{x_i-x_j}
$$
\end{theorem}

\begin{exercise}
Let $\F_{31} = \Z/31\Z$ be the finite field of $31$ elements,
and let
$$
\{(1,1), (2,16), (3,25), (4,28)\}
$$
be a set of pairs of the form $(i,f(i))$ for some polynomial $f(x)$.
\begin{enumerate}
\item
Find the value $f(0)$ of the polynomial $f(x)$ of degree $2$
which interpolates the first three points.
\item
Find the polynomial $f(x)$ of degree $2$ which interpolates
the first three points.
\item
Show that the same polynomial passes through the fourth point.
\item
Use the Lagrange interpolation theorem to conclude that $f(x)$
is the unique polynomial of degree less than $4$ which passes
through these four points.
\end{enumerate}
\end{exercise}

\begin{proof}[Solution]
Let $\F_{31} = \Z/31\Z$ be the finite field of $31$ elements, and let
$$
\{(1,1), (2,16), (3,25), (4,28)\}
$$
be a set of pairs of the form $(i,f(i))$ for some polynomial $f(x)$.

\begin{enumerate}
\item
The value $f(0)$ of the polynomial $f(x)$ of degree $2$ which
interpolates the first three points is given, using the first three
shares, by
$$
\begin{aligned}
f(0) &
     =  1 \cdot \frac{(2)(3)}{(2-1)(3-1)}
     + 16 \cdot \frac{(1)(3)}{(1-2)(3-2)}
     + 25 \cdot \frac{(1)(2)}{(1-3)(2-3)}\\
     &
     =  1 \cdot (3)
     + 16 \cdot (-3)
     + 25 \cdot (1) = 3 + 14 + 25 = 11.
\end{aligned}
$$
Using the last three shares we find:
$$
\begin{aligned}
f(0) &
     = 16 \cdot \frac{(3)(4)}{(3-2)(4-2)}
     + 25 \cdot \frac{(2)(4)}{(2-3)(4-3)}
     + 28 \cdot \frac{(2)(3)}{(2-4)(3-4)}\\
     &
     = 16 \cdot (6)
     + 25 \cdot (-8)
     + 28 \cdot (3) = 3 + 17 + 22 = 11.
\end{aligned}
$$
N.B. Be careful to do any inversions modulo 31!!
\item
Using the full formula, we get $f(x) = 28x^2 + 24x + 11$.
\item
Verify: $f(4) = 28 \cdot 4^2 + 24 \cdot 4 + 11 = 14 + 3 + 11 = 28.$
\item
Since the polynomial $f(x)$ agrees with the {\it four} points,
this must be the unique polynomial of degree less than four which
does so.
\end{enumerate}
\end{proof}
